#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 标准线性基
class XORBase
{
private:
    int L;
    vector<int> bs;
    bool ld;

public:
    XORBase(int l) : L(l), bs(l), ld(false) {}
    bool add(int x)
    {
        for (int i = 0; i < L; i++)
        {
            if ((x >> i) & 1)
            {
                if ((bs[i] >> i) & 1)
                    x ^= bs[i];
                else
                {
                    bs[i] = x;
                    return true;
                }
            }
        }
        ld = true;
        return false;
    }

    bool linearly_independent()
    {
        return ld;
    }
};

// 异或方程，l 为未知数的个数
// 时间复杂度为 n^2
class XOREquation
{
    using BRow = bitset<2005>;

private:
    vector<BRow> bs;
    int L;

public:
    XOREquation(int l) : bs(l + 1), L(l) {}
    bool add(BRow row)
    {
        for (int i = 1; i <= L; i++)
        {
            if (row[i] == 0)
                continue;
            if (bs[i][i] == 0)
            {
                bs[i] = row;
                return true;
            }
            row ^= bs[i];
        }
        return false;
    }

    bool solve(vector<int> &ans)
    {
        if (bs[L][L] == 0)
            return false;
        ans.resize(L + 1);
        for (int i = L; i >= 1; i--)
        {
            if (bs[i][i] == 0)
                return false;
            int k = bs[i][L + 1];
            for (int j = i + 1; j <= L; j++)
            {
                if (bs[i][j])
                    k ^= ans[j];
            }
            ans[i] = k;
        }
        return true;
    }
};
